package hot150;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedHashSet;

// https://leetcode.cn/problems/remove-duplicates-from-sorted-array/?envType=study-plan-v2&envId=top-interview-150
public class q3 {

    public int removeDuplicates(int[] nums) {
//        return method1(nums, nums.length);
//        return method2(nums, nums.length);
        return method3(nums, nums.length);
    }

    /**
     * HashSet -> LinkedHashSet
     * 3ms
     * 复杂度O(n)
     */
    public int method1(int[] nums, int n) {
        HashSet<Integer> set = new LinkedHashSet<>(n);
        for (int num : nums) {
            set.add(num);
        }
        int i = 0;
        for (Integer num : set) {
            nums[i++] = num;
        }
        return i;
    }

    /**
     * HashSet + 指针
     * 2ms
     * 复杂度O(n)
     */
    public int method2(int[] nums, int n) {
        HashSet<Integer> set = new HashSet<>(n);
        int i = 0;
        for (int num : nums) {
            if (!set.contains(num)) {
                set.add(num);
                nums[i++] = num;
            }
        }
        return i;
    }

    /**
     * 双指针 -> 非严格递增
     * 0ms
     * 复杂度O(n)
     */
    public int method3(int[] nums, int n) {
        int i, j;
        i = j = 0;
        while (j < n) {
            int k = j;
            // 判断重复元素
            while (j < n && nums[j] == nums[k]) {
                j++;
            }
            // 走完所有重复的值，赋值给i
            nums[i++] = nums[k];
        }
        return i;
    }

    public static void main(String[] args) {
        int[] nums = {1,1,2};
        System.out.println(new q3().removeDuplicates(nums));
        System.out.println(Arrays.toString(nums));
    }

}
